package main.leetcode.clockin.September;

import java.util.ArrayList;
import java.util.List;

/**
 * 60. 第k个排列
 *
 * <p>给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
 *
 * <p>按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 * <p>"123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第 k 个排列。
 *
 * <p>说明：给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。
 *
 * <p>示例 1: 输入: n = 3, k = 3 输出: "213"
 *
 * <p>示例 2: 输入: n = 4, k = 9 输出: "2314"
 */
public class day5 {
    private String res;
    private int cnt;

    public static void main(String[] args) {
        System.out.println(new day5().getPermutation(3, 3));
        System.out.println(new day5().getPermutation(4, 9));
        System.out.println(new day5().getPermutation(3, 1));
    }

    public String getPermutation(int n, int k) {
        // 计算阶乘，n!
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        // 记录每轮剩余的num序列
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            nums.add(i);
        }

        StringBuilder res = new StringBuilder();
        for (int i = n - 1; i >= 0; --i) {
            int index = (k - 1) / factorial[i];
            res.append(nums.remove(index));
            // 减去以 nums[i] (i < index) 为起始的排列
            k -= factorial[i] * index;
        }
        return res.toString();
    }

    //    /** 回溯 */
    //    public String getPermutation(int n, int k) {
    //        boolean[] isVisited = new boolean[n + 1];
    //        backTrack(new StringBuilder(), isVisited, n, k);
    //        return res;
    //    }
    //
    //    private void backTrack(StringBuilder cur, boolean[] isVisited, int n, int k) {
    //        if (res != null) {
    //            return;
    //        }
    //        if (cur.length() == n) {
    //            if (++cnt == k) {
    //                res = cur.toString();
    //            }
    //        }
    //        for (int i = 1; i <= n; i++) {
    //            if (!isVisited[i]) {
    //                isVisited[i] = true;
    //                cur.append(i);
    //                backTrack(cur, isVisited, n, k);
    //                cur.deleteCharAt(cur.length() - 1);
    //                isVisited[i] = false;
    //            }
    //        }
    //    }
}
